using System;
using System.Collections.Generic;
using System.Linq;
using System.Threading.Tasks;

namespace DataStructure
{
    public class Sort
    {
        /// <summary>
        /// 冒泡排序
        /// 时间复杂度：O(n^2)
        /// 空间复杂度：O(1)
        /// </summary>
        /// <param name="arr"></param>
        public static void BubbleSort(int[] arr)
        {
            int n = arr.Length;

            for (int i = 0; i < n; i++)
                for (int j = 0; j < n - i - 1; j++)
                    if (arr[j] > arr[j + 1])
                        (arr[j + 1], arr[j]) = (arr[j], arr[j + 1]);
        }


        /// <summary>
        /// 选择排序
        /// 时间复杂度：O(n^2)
        /// 空间复杂度：O(1)
        /// </summary>
        /// <param name="arr"></param>
        public static void SelectSort(int[] arr)
        {
            int n = arr.Length;

            for (int i = 0; i < n - 1; i++) // 最后一个元素不需要再排序
            {
                // 最小元素的索引min 从未排序的第一个位置i开始寻找
                int min = i;

                for (int j = i + 1; j < n; j++)
                {
                    if (arr[j] < arr[min])
                        min = j;
                }

                // 将找到的最小元素交换到未排序序列的起始位置
                if (min != i)
                {
                    (arr[min], arr[i]) = (arr[i], arr[min]);
                }
            }
        }

        /// <summary>
        /// 插入排序
        /// 时间复杂度：O(n^2)
        /// 空间复杂度：O(1)
        /// </summary>
        /// <param name="arr"></param>
        public static void InsertSort(int[] arr)
        {
            int n = arr.Length;

            for (int i = 1; i < n; i++) // 从第二个元素开始插入
            {
                int key = arr[i]; // 当前待插入的元素
                int j = i - 1;

                // 将当前元素与已排序部分的元素从后向前逐一比较
                while (j >= 0 && arr[j] > key)
                {
                    arr[j + 1] = arr[j]; // 将较大的元素后移
                    j = j - 1;
                }

                // 将当前元素插入到正确的位置
                arr[j + 1] = key;
            }
        }

        /// <summary>
        /// 希尔排序
        /// 时间复杂度：O(n log n) ~ O(n^2)，取决于增量序列
        /// 空间复杂度：O(1)
        /// </summary>
        /// <param name="arr"></param>
        public static void ShellSort(int[] arr)
        {
            int n = arr.Length;

            // 使用希尔增量，即每次都减半
            for (int gap = n / 2; gap > 0; gap /= 2)
            {
                // 对每个子序列进行插入排序
                for (int i = gap; i < n; i++)
                {
                    int temp = arr[i];
                    int j;
                    for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                    {
                        arr[j] = arr[j - gap];
                    }
                    arr[j] = temp;
                }
            }
        }

        /// <summary>
        /// 归并排序
        /// 时间复杂度：O(nlogn)
        /// 空间复杂度：O(n)
        /// </summary>
        /// <param name="arr"></param>
        /// <param name="left"></param>
        /// <param name="right"></param>
        public static void MergeSort(int[] arr, int left, int right)
        {
            if (left < right)
            {
                int mid = left + (right - left) / 2;

                // 递归排序左半部分
                MergeSort(arr, left, mid);

                // 递归排序右半部分
                MergeSort(arr, mid + 1, right);

                // 合并两个有序部分
                Merge(arr, left, mid, right);
            }
        }

        public static void Merge(int[] arr, int left, int mid, int right)
        {
            int n1 = mid - left + 1;
            int n2 = right - mid;

            // 创建临时数组
            int[] L = new int[n1];
            int[] R = new int[n2];

            // 拷贝数据到临时数组
            Array.Copy(arr, left, L, 0, n1);
            Array.Copy(arr, mid + 1, R, 0, n2);

            // 合并临时数组到原数组
            int i = 0, j = 0, k = left;
            while (i < n1 && j < n2)
            {
                if (L[i] <= R[j])
                {
                    arr[k] = L[i];
                    i++;
                }
                else
                {
                    arr[k] = R[j];
                    j++;
                }
                k++;
            }

            // 拷贝剩余元素
            while (i < n1)
            {
                arr[k] = L[i];
                i++;
                k++;
            }

            while (j < n2)
            {
                arr[k] = R[j];
                j++;
                k++;
            }
        }

        /// 快速排序
        /// 时间复杂度：O(nlogn)
        /// 空间复杂度：O(logn)
        /// </summary>
        /// <param name="arr"></param>
        public static void QuickSort(int[] arr)
        {
            QuickSort(arr, 0, arr.Length - 1);
        }

        private static void QuickSort(int[] arr, int low, int high)
        {
            if (low < high)
            {
                int pivotIndex = Partition(arr, low, high);
                QuickSort(arr, low, pivotIndex - 1);  // 递归排序左子数组
                QuickSort(arr, pivotIndex + 1, high); // 递归排序右子数组
            }
        }
        private static int Partition(int[] arr, int low, int high)
        {
            int pivot = arr[low]; // 选择第一个元素作为基准值
            int i = low + 1;      // i 指向大于等于基准值的第一个元素

            for (int j = low + 1; j <= high; j++)
            {
                if (arr[j] < pivot)
                {
                    Swap(arr, i, j);
                    i++;
                }
            }

            Swap(arr, low, i - 1);
            return i - 1;
        }



        /// <summary>
        /// 堆排序(1)
        /// </summary>
        /// 时间复杂度：O(nlogn) (建堆和出堆)
        /// 空间复杂度：O(N)
        /// <param name="arr"></param>
        public static void HeapSor1(int[] arr)
        {
            int n = arr.Length;

            MaxHeap<int> maxHeap = new MaxHeap<int>(n);

            for (int i = 0; i < n; i++)
                maxHeap.Insert(arr[i]);

            for (int i = n - 1; i >= 0; i--)
                arr[i] = maxHeap.RemoveMax();
            //arr最终升序排列
        }

        /// <summary>
        /// 堆排序(2)
        /// 时间复杂度：O(nlogn)
        /// 空间复杂度：O(1)
        /// </summary>
        /// <param name="arr"></param>
        public static void HeapSort2(int[] arr)
        {

            int n = arr.Length;

            // 先将原数组整理成最大堆
            // 从最后一个非叶子节点开始，向下调整
            for (int i = (n - 1 - 1) / 2; i >= 0; i++)
                Sink(arr, i, n - 1);
            // 原地的堆排序
            // 从最后一个元素开始，逐个将堆顶元素（最大值）移到数组末尾
            for (int i = n - 1; i >= 0; i--)
            {
                Swap(arr, 0, i);
                Sink(arr, 0, i - 1);
            }
        }

        //元素下沉
        private static void Sink(int[] arr, int k, int N)
        {
            while (2 * k + 1 <= N)
            {
                int j = 2 * k + 1;

                if (j + 1 <= N && arr[j + 1].CompareTo(arr[j]) > 0) j++;

                if (arr[k].CompareTo(arr[j]) >= 0) break;

                Swap(arr, k, j);

                k = j;
            }
        }
        private static void Swap(int[] arr, int i, int j)
        {
            (arr[j], arr[i]) = (arr[i], arr[j]);
        }
    }
}